\documentclass[revision]{FPSAC2017}

\articlenumber{2}
\addbibresource{02_Davis_Sagan.bib}

\usepackage{tikz}

\theoremstyle{definition}
\newtheorem{thm}{Theorem}[section]
\newtheorem{algorithm}[thm]{Algorithm}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{claim}[thm]{Claim}
\newtheorem{example}[thm]{Example}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{construction}[thm]{Construction}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{defn}[thm]{Definition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{obs}[thm]{Observation}
\newtheorem{question}[thm]{Question}
\newtheorem{remark}[thm]{Remark}

% define math operators
\DeclareMathOperator{\aff}{aff}
\DeclareMathOperator{\alt}{alt}
\DeclareMathOperator{\AltAv}{\widetilde{Av}}
\DeclareMathOperator{\Av}{Av}
\DeclareMathOperator{\Bose}{Bose}
\DeclareMathOperator{\cn}{cone}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\Des}{Des}
\DeclareMathOperator{\EV}{EV}
\DeclareMathOperator{\des}{des}
\DeclareMathOperator{\face}{face}
\DeclareMathOperator{\gglex}{\succ_{grevlex}}
\DeclareMathOperator{\lglex}{\prec_{grevlex}}
\DeclareMathOperator{\lex}{<_{lex}}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\Int}{Int}
\DeclareMathOperator{\inte}{int}
\DeclareMathOperator{\Irr}{Irr}
\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\ehr}{\mathcal{L}}
\DeclareMathOperator{\grob}{\mathcal{G}}
\DeclareMathOperator{\init}{\mathrm{in}_{\prec}}
\DeclareMathOperator{\Inv}{\mathrm{Inv}}
\DeclareMathOperator{\pos}{pos}
\DeclareMathOperator{\rad}{rad}
\DeclareMathOperator{\stab}{stab}
\DeclareMathOperator{\Stab}{Stab}
\DeclareMathOperator{\SYT}{SYT}
\DeclareMathOperator{\vol}{vol}
\DeclareMathOperator{\Vol}{Vol}


%define new commands
\newcommand{\A}{\mathcal{A}}
\newcommand{\AltB}{\widetilde{B}}
\newcommand{\AltQ}{\widetilde{Q}}
\newcommand{\AltT}{\widetilde{\mathcal{T}}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\FF}{\mathcal{F}}
\newcommand{\HH}{\mathcal{H}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\MM}{\mathcal{M}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\W}{\overline{W}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\symm}{\mathfrak{S}}
\newcommand{\TT}{\mathcal{T}}
\newcommand{\LL}{\mathcal{L}}
\newcommand{\dprime}{\prime\prime}
\newcommand{\da}{\hspace{-2pt}\downarrow}
\newcommand{\cF}{\mathcal F}
\newcommand{\iso}{\cong}
\newcommand{\wc}{\widetilde{c}}
\newcommand{\wb}{\widetilde{\beta}}
\newcommand{\om}{\omega}
\newcommand{\Om}{\Omega}
\newcommand{\ol}{\overline}
\newcommand{\sig}{\sigma}
\newcommand{\sigp}{\sigma^{\prime}}
\newcommand{\taup}{\tau^{\prime}}

\newcommand{\tre}{\textcolor{red}}
\newcommand{\tbl}{\textcolor{blue}}

\title{Pattern-Avoiding Polytopes}

\author{Robert Davis\thanks{\href{mailto:davisr@math.msu.edu}{davisr@math.msu.edu}} \and Bruce Sagan\thanks{\href{mailto:sagan@math.msu.edu}{sagan@math.msu.edu}}}

\address{Department of Mathematics, Michigan State University, East Lansing, MI}

\received{October 16, 2016}

\revised{\today}

\abstract{
	The Birkhoff polytope is a long-studied polytope connected to many areas of mathematics.
	In this paper, we generalize it by considering convex hulls of subsets of its vertices. 
	The vertices chosen correspond to avoidance classes of permutations.
	We study the structure of two special cases, leading to connections with shellable order complexes, toric ideals, standard Young tableaux, and $(P,\omega)$-partitions.
	We also find that these polytopes have palindromic and unimodal $h^*$-vectors.
	}


\keywords{lattice polytope, permutation pattern, toric ideal, shellable poset, Ehrhart series, unimodal sequence}

\begin{document}


\maketitle

\section{Introduction}

Let $\symm_n$ denote the symmetric group on $1,2,\dots,n$ and $\symm = \symm_1 \cup \symm_2 \cup \cdots$.
Let $\pi  \in \symm_k$ and $\sig \in \symm_n$.
We say that $\sig$ {\em contains the pattern} $\pi$ if there is some substring $\sig'$ of $\sig$ whose elements have the same relative order as those in $\pi$.
If there is no such substring then we say that $\sig$ {\em avoids the pattern} $\pi$.
If $\Pi \subseteq \symm$, then we say $\sig$ {\em avoids} $\Pi$ if $\sig$ avoids every element of $\Pi$.
We denote by 
\[\Av_n(\Pi) := \{\sig \in \symm_n\ |\ \sig \text{ avoids } \Pi \}\]
the {\em avoidance class} of $\Pi$.

A polytope $P \subseteq \RR^n$ is the convex hull of finitely many points, written as $P = \conv\{v_1,\ldots, v_k\}$.
Equivalently, a polytope may be described as a bounded intersection of finitely many half-spaces.
The {\em dimension} of $P$ is the dimension of its affine span.
An affine hyperplane $l(x) = b$ is called {\em supporting} if $l(p) \geq b$ for every $p \in P$.
If $l(x) = b$ is a supporting hyperplane, then the set $\{l(x) = b\} \cap P$ is called a {\em face} of $P$ and is a subpolytope of $P$.
Faces of dimension $0$ are {\em vertices}, faces of dimension $1$ are called {\em edges}, and faces of dimension $\dim P - 1$ are called {\em facets}.
Additionally, we say a polytope is {\em lattice} if each vertex is an element of $\ZZ^n$.

Lattice polytopes have long found connections with permutations, in particular via the Birkhoff polytope: the convex hull of the $n\times n$ permutation matrices. 
In this abstract, we generalize this class of polytopes by taking convex hulls of vertices corresponding to avoidance classes of permutations.

For a lattice polytope $P \subseteq \RR^n$, consider the counting function $\ehr_P(m) := |mP \cap \ZZ^n|$, where $mP$ is the $m$-th dilate of $P$.
This function is a polynomial in $m$, called the {\em Ehrhart polynomial} of $P$.
In particular, two well-known theorems due to Ehrhart~\cite{Ehrhart} and Stanley~\cite{StanleyDecompositions} imply that the {\em Ehrhart series} of $P$, $E_{P}(t) := 1 + \sum_{m\ge1} \ehr_P(m)t^m,$
may be written in the form
\[
	E_P(t)=\frac{\sum_{j=0}^d h_j^*t^j}{(1-t)^{\dim P+1}} \, .
\]
for some nonnegative integers $h_0^*,\ldots,h_d^*$ with $h_0^*=1$, $h_d^* \neq 0$, and $d \leq \dim P$. 
	
We say the polynomial $h^*_P(t):=\sum_{j=0}^dh_j^*t^j$ is the {\em $h^*$-polynomial} of $P$ and the vector of coefficients, $h^*(P)$, is the \emph{$h^*$-vector} of $P$.
The $h^*$-vector of a lattice polytope $P$ is a fascinating invariant, and obtaining a general understanding of $h^*$-vectors of 	lattice polytopes and their geometric/combinatorial implications is currently of great interest.

Beginning in \cref{sec:birkhoff}, we describe a natural blending of pattern avoidance with the Birkhoff polytope with the goal of determining the behavior of its $h^*$-vector in some interesting cases.
This is difficult to do directly, and so we take a detour to study certain helpful triangulations using toric algebra. 
Finally, in \cref{sec:gorensteinsection}, we connect these triangulations with a result in the theory of $(P,\omega)$-partitions which allows us to identify the behavior of the $h^*$-vector.
We have found interesting results  for other sets of patterns, as well as for an analogous generalization of the permutohedron, but space limitations prevent their discussion in this abstract.
For details, see~\cite{DavisSagan}.

\section{The Birkhoff Polytope}\label{sec:birkhoff}

We begin by merging the Birkhoff polytope with avoidance classes of permutations.

\begin{defn}
	Let $\Pi$ be any set of permutations.
	The {\em $\Pi$-avoiding Birkhoff polytope} is
	\[
		B_n(\Pi) := \conv\{M \in \RR^{n\times n}\ |\ M \text{ is the permutation matrix for some } \sig \in \Av_n(\Pi)\}.
	\]
\end{defn}

We will be devoting our study to $B_n(132,312)$ and one other class of polytopes, for which we will require some more definitions and notation.
We say a permutation $\sig = a_1\cdots a_n$ is {\em alternating}, or {\em up-down}, if $a_1 < a_2 > a_3 < \cdots$.
In the interest of compact notation, we will write $\AltAv_n(\Pi)$ for alternating permutations that avoid $\Pi$ and $\AltB_n(\Pi)$ for the analogous variation of $B_n(\Pi)$.

This brings us to our second class, $\AltB_n(123)$. 
Without much difficulty, one can show that the projection of $\AltB_n(123)$ to $\AltB_{n-1}(123)$, defined by dropping row $n$ and column $n-1$ of the matrices, preserves the Ehrhart polynomial. 
So it will suffice to study the case when $n$ is even.

\subsection{Sublattices of the Weak Order}\label{subsec:weak order}

Recall that the {\em right} (respectively, {\em left}) {\em weak (Bruhat) order} on $\symm_n$ is defined by the cover relations $\sig_1 \lessdot \sig_2$ if there is a simple transposition $s_i$ such that $\sig_1s_i = \sig_2$ (respectively, $s_i\sig_1 = \sig_2$) and $\inv(\sig_2) = \inv(\sig_1) + 1$.  Here, $\inv\sig$ is the number of inversions of $\sig$.

Let $Q_n(\Pi)$ denote the poset obtained by restricting the right weak order to $\Av_n(\Pi)$. 
Similarly define $\AltQ_n(\Pi)$ for the left weak order on $\AltAv_n(\Pi)$.
Inequalities involving permutation matrices are meant to refer to these two partial orders on the corresponding permutations.

We will find two classes of previously-studied posets useful, so we define them now.
Let $M(n)$ denote the poset of shifted Young diagrams with largest part at most $n$, ordered by inclusion.
These are the posets described in Exercise~3.187(a) in~\cite{StanleyVol1} and studied using linear algebra in~\cite{Proctor}.
In particular, $M(n)$ is a distributive lattice since it is a principle lower order ideal in the shifted version of Young's lattice.

For the other class of useful posets, let $D(k)$ denote the poset of (left-justified) Young diagrams fitting inside the shape $(k-1,k-2,\dots,1)$, ordering by inclusion.
Again, one sees easily that these are distributive lattices.

\begin{prop}\label{prop:distributive}
	For all $n$, $Q_n(132,312) \iso M(n-1)$ and $\AltQ_n(123) \iso D(\lceil n/2 \rceil)$.
	Thus, $Q_n(132,312)$ and $\AltQ_n(123)$ are distributive lattices. \qed
\end{prop}

For a general finite distributive lattice $L$ of rank $n$, it is well-known that there exists an $n$-element poset $P$ for which $L \cong J(P)$, where $J(P)$ is the lattice of order ideals of $P$.
The poset $P$ can be taken to be the join-irreducible elements of $L$ and using the order relation from $L$ restricted to these elements. 
Denote the poset of join-irreducibles of $L$ by $\Irr(L)$.
For simplicity, we identify the join-irreducibles of $Q_n(132,312)$ with the join-irreducibles of $M(n-1)$, and likewise identify the join-irreducibles of $\AltQ_n(123)$ and $D(\lceil n/2 \rceil)$.

Let us now determine the join irreducibles of our two lattices.  
Using the Young diagram interpretation of both, an element is join irreducible precisely when the shape has exactly one inner corner, that is, a box in row $b$ and column $c$, which we will refer to as $(b,c)$, such that neither $(b+1,c)$ nor $(b,c+1)$ is in the shape.
Identifying these diagrams with the coordinates of their unique inner corners, the induced partial order on both posets of join irreducibles is component-wise.
For the remainder of this paper, the join irreducibles of $Q_n(132,312)$ and $\AltQ_n(123)$ will be identified with the elements of these posets.

\subsection{Triangulations, Shellabililty, and EL-labelings}\label{subsec:EL and shellable}

In this section we will use the posets $Q_n(132,312)$ and $\AltQ_n(123)$ to carefully decompose $B_n(132,312)$ and $\AltB_n(123)$.
First, we recall some definitions and concepts in geometry and poset topology.

A {\em polytopal complex} $\FF$ is a finite nonempty collection of polytopes such that 
\begin{enumerate}
	\item if $P \in \FF$, then every face of $P$ is in $\FF$, and
	\item if $P, Q \in \FF$, then $P \cap Q$ is a face of both $P$ and $Q$.
\end{enumerate}
A commonly-considered polytopal complex is the {\em face complex} $\FF(P)$ of a polytope $P$, whose elements are all faces of $P$.

A {\em triangulation} of a polytopal complex $\FF$ is a geometric simplicial complex $\Delta$ with vertices those of $\FF$ and underlying space equal to the union of the faces of $\FF$,
such that every face of $\Delta$ is contained in a face of $\FF$.
A triangulation of the face complex $\FF(P)$ of a polytope $P$ is simply called a {\em triangulation} of $P$.
A lattice simplex is called {\em unimodular} if its volume is $1$ when normalized for the lattice it spans, and a triangulation is called {\em unimodular} if each simplex it contains is unimodular.
Therefore, if $P$ has a unimodular triangulation $\mathcal{T}$, then its normalized volume is equal to the number of maximal simplices in $\mathcal{T}$.

Now, the {\em order complex} $\Delta(Q)$ of a poset $Q$ is the simplicial complex of chains in $Q$.
A simplicial complex is {\em shellable} if its maximal faces are of the same dimension and can be ordered as $F_1,\ldots,F_k$ such that for each $i=1,\ldots, k-1$, 
$F_{i+1} \cap (\cup_{j=1}^i F_j)$ is a nonempty union of facets of $F_{i+1}$.
A poset is called {\em shellable} if its order complex is shellable.

To show that $Q_n(132,312)$ and $\AltQ_n(123)$ are shellable we will make use of the existence of a particular labeling of the edges in their Hasse diagrams.
If $Q$ is a poset, set
\[
	E(Q) := \{(q_1,q_2) \in Q\times Q \ |\ q_1 \lessdot q_2\},
\] 
thought of as the edges of the Hasse diagram of $Q$.
An {\em edge labeling} of $Q$ by $\ZZ$ is a function $\lambda: E(Q) \to \ZZ$.
A saturated chain $q_0 \lessdot q_1 \lessdot \cdots \lessdot q_k$ in $Q$ is called {\em increasing} if $\lambda(q_0,q_1) < \lambda(q_1,q_2) < \cdots < \lambda(q_{k-1},q_k)$.
An {\em EL-labeling} of a poset $Q$ is an edge labeling such that every interval $[x,y]$ in $Q$ has a unique increasing maximal chain 
which lexicographically precedes all other maximal chains of $[x,y]$.
Posets admitting an EL-labeling are shellable and are usually referred to as {\em EL-shellable}.

We will use EL-shellable posets to decompose $B_n(132,312)$ and $\AltB_n(123)$ in specific ways in \cref{sec:gorensteinsection}.
Fortunately, specific EL-shellings of $Q_n(132,312)$ and $\AltQ_n(123)$ are available using a technique from~\cite{StanleySupersolvable}.
A {\em natural labeling} of a poset $P$ with $|P|=n$ is an order-preserving bijection  $\om:P\rightarrow[n]$.
Let $L$ be a finite distributive lattice so that $L \iso J(P)$ where $P$ is the poset of join irreducibles, and let $\om$ be a natural labeling of $P$.
Then we have a cover of order ideals $I\lessdot J$ in $L$ if and only if $J  -  I =\{x\}$ for some $x\in P$.  Give the cover the label $\lambda(I,J)=\om(x)$. 
This edge labeling is an EL-labeling for $L$. 


To apply this process we will use the natural labeling of the join-irreducibles in $\Irr(Q_n(132,321))$ given by
\[ \om(b,c) = (b-1)n  + c + 1 - \binom{b+1}{2}  \]
and in $\Irr(\AltQ_n(123))$ for $n$ even by
\[ \om(b,c) = \frac{(b-1)(n-b)}{2}+ c.\]
To simplify notation, we will often identify maximal chains $c: q_0 \lessdot q_1 \lessdot \dots \lessdot q_k$ in $Q_n(132,312)$ and $\AltQ_n(123)$ 
with their sequences of edge labels \[\lambda(c)=(\lambda(q_0,q_1), \lambda(q_1,q_2), \dots, \lambda(q_{k-1},q_k)).\]

We now take a first step in constructing a bridge from purely combinatorial information of these simplicial complexes to geometric information about $B_n(132,312)$ and $\AltB_n(123)$. 
The next result is proved by an inductive argument based on the lexicographic order of the maximal simplices in the corresponding order complexes.


\begin{prop}\label{prop:unimodularity}
	Let $f: \Delta(Q_n(132,312)) \to \RR^{n \times n}$ be the function 
	\[
		f(\{\sig_1,\dots,\sig_u\}) = \conv\{M_{\sig_1}, \dots , M_{\sig_u}\},
	\]
	where $M_{\sig_i}$ is the matrix for $\sig_i$.
	The collection
	\[
		\TT_n(132,312) := \{ f(\Gamma)\ |\ \Gamma \in \Delta(Q_n(132,312))\}
	\]
	is a set of simplices contained in $B_n(132,312)$, where each $f(\Gamma)$ is unimodular with respect to the affine lattice 
	$\aff(f(\Gamma)) \cap \ZZ^{n\times n}$.
	The collection $\AltT_n(123)$, defined similarly, is a collection of unimodular simplices in $\AltB_n(123)$. \qed
\end{prop}

%One may show directly that $\dim B_n(132,312) \le \binom{n}{2}$ and $\dim \AltB_n(123) \le \binom{\lceil n/2 \rceil}{2}$.
%The above proposition implies the reverse inequalities, so together we have the following.

%\begin{thm}\label{thm:dimension equalities}
%	For all $n$ we have $\dim B_n(132,312) = \binom{n}{2}$ and $\dim \AltB_n(123) = \binom{\lceil n/2 \rceil}{2}$.
%So the simplices in $\TT_n(132,312)$ are unimodular with respect to $\aff B_n(132,312)\cap \ZZ^{n\times n}$ 
%and similarly for $\AltB_n(123)$.
%\hfill\qed
%\end{thm}

We would like to show that $\TT_n(132,312)$ and $\AltT_n(123)$ are actually unimodular triangulations of their respective polytopes.
To do so, we will use techniques from toric algebra, but first make the following note: if a lattice polytope $P$ does have unimodular triangulation, then it follows quickly that it has the {\em integer decomposition property} (or {\em is IDP}), that is, for all positive integers $m$ and any $x \in mP \cap \ZZ^n$, there exist $m$ points in $P \cap \ZZ^n$ whose sum is $x$.


\subsection{Toric Algebra}\label{sec:toric algebra}

The methods we will use to show $\TT_n(132,312)$ and $\AltT_n(123)$ are unimodular triangulations of their respective polytopes require a bit of algebra background.
First, let $\A = \{l_1,\dots,l_s\} \subseteq \ZZ^n$.
We may define $k[\A] := k[x^{l_1},\ldots,x^{l_s}]$, to be considered as contained in the ring of Laurent polynomials $k[x_1^{\pm},\ldots,x_n^{\pm}]$,
where $k$ is a field and $x^{(v_1,\ldots,v_n)} = \prod x_i^{v_i}$.
It turns out that it is helpful to study $\A$ by first defining $T_{\A} = k[t_1,\dots,t_s]$ and the map $\phi: T_{\A} \to k[\A]$ by $\phi(t_i) = x^{l_i}$, since then we have
\[
	T_{\A} / \ker \phi \iso k[\A].
\]
The ideal $I_{\A} := \ker \phi$ is the {\em toric ideal} of $\A$, and has been studied extensively in part due to its uses in algebraic statistics, algebraic geometry, and convex polytopes.

If $P$ is a lattice polytope then we set $\A_P = (P,1) \cap \ZZ^{n+1}$, and 
\[
	k[\cn(P)] := k[x^az^m\ |\ a \in mP \cap \ZZ^n] \subseteq k[x_1^{\pm},\ldots,x_n^{\pm},z],
\]
an algebra graded by the exponent of the new variable $z$. So when $P$ is IDP we have $k[\cn(P)] = k[\A_P]$.
However, this equality does not hold if $P$ is not IDP, since then the monoid generated by $\A_P$ does not generate all elements of $\cn(P)\cap \ZZ^{n+1}$.
To remedy this we have to introduce the {\em Hilbert basis} of $\cn(P)$, which is the unique minimal-cardinality set $\HH \subseteq \cn(P) \cap \ZZ^{n+1}$ such that every lattice point of $\cn(P)$ is a $\ZZ_{\geq 0}$-linear combination of elements of $\HH$.
The existence and uniqueness of the Hilbert basis can be proved using the Hilbert Basis Theorem.

This allows us to define the toric ideal of a polytope $P$:
Suppose the Hilbert basis of $\cn(P)$ is $\HH=\{(v_1,w_1),\dots,(v_r,w_r)\} \subseteq \ZZ^n \times \ZZ$. 
We have $T_{\HH} / I_P \iso k[\cn(P)],$ where $I_P = \ker \phi$ is the {\em toric ideal} of $P$.
If $P$ is IDP, then $I_P = I_{\A_P}$, but in general only $I_P\supseteq I_{\A_P}$.

One significant advantage of studying the toric ideal of more general sets $\A$ is due to its ability to create triangulations of $\conv \A$, using only the points from $\A$, under sufficient conditions. 
Specifically, if there is some $\nu = (\nu_1,\dots,\nu_n) \in \RR^n$ 
such that $\nu^Tl_i = 1$ for each $l_i \in \A$, we call $\A$ a {\em point configuration}, or simply a {\em configuration} if there is no risk of confusion.
When $\A$ is a configuration,  then the {\em positive span}
\[
	\pos(\A) := \left\{ \sum_{i=1}^s \lambda_il_i\ |\ \lambda_i \geq 0 \text{ for all } i \right\} \subseteq \RR^n
\]
is a polyhedral cone (differing from $\cn(\A)\subseteq \RR^{n+1}$) containing no positive-dimensional subspace, so a Hilbert basis exists.
If $\A$ is not a configuration, then $\pos(\A)$ is still a cone but now contains a nontrivial subspace, so a Hilbert basis does not exist since a minimal generating set of $\pos(\A) \cap \ZZ^n$ is no longer unique.
Note that for any polytope $P$ in $\RR^n$, the set $\A_P$ is a configuration since it satisfies $e_{n+1}^Tv = 1$ for each $v \in \A_P$.


Techniques from toric algebra will provide the tools for a critical step in proving that
the collections of simplices introduced in the previous section actually form unimodular triangulations of their respective polytopes.  In particular,
when $P$ is one of these polytopes, we will use $I_{\A_P}$ to identify a triangulation of $\conv \A_P$, using only the elements of $\A_P$.
In this case, since $P$ is a subpolytope of $[0,1]^{n \times n}$, it contains no lattice points other than its vertices.
So, $\A_P$ consists exactly of the vertices of $(P,1)$, and a triangulation of $\conv \A_P$ is automatically a triangulation of $(P,1)$, which in turn induces a triangulation of $P$ by projecting each simplex back into $\RR^{n \times n}$.
The triangulation of $P$ will be unimodular with respect to the lattice generated by $\ZZ$-linear combinations of the elements of $P$.
Observing that this triangulation consists exactly of the simplices in $\TT_n(132,312)$ (respectively, $\AltT_n(123)$), 
%\cref{thm:dimension equalities}
we will have shown that the triangulations are unimodular with respect to the affine lattice $B_n(132,312) \cap \ZZ^{n\times n}$ (respectively, $\AltB_n(123) \cap \ZZ^{n \times n}$).


Returning to the general development, 
when $S \subseteq \RR^n$ is a unimodular simplex, it is not difficult to show that $\A_S$ is the Hilbert basis of $\cn(S)$.
When $P$ is a general lattice polytope, we only know a priori that $\A_P$ must be contained in the Hilbert basis of $\cn(P)$.
When a triangulation $\TT$ of $P$ is known, each lattice point $x \in \cn(P)$ lies in $\cn(S)$ for some $S \in \TT$.
If $S$ is unimodular, then $x$ may be written as a sum of just the elements in $(S,1) \cap \ZZ^{n+1} \subseteq \A_P$.
Thus, if $\TT$ is a unimodular triangulation, $x$ can always be expressed as a sum of elements in $\A_P$, so $\A_P$ is exactly the Hilbert basis of $\cn(P)$.
Therefore, in this case, any properties of $(\TT,1)$ as a unimodular triangulation with respect to $\aff \A_P \cap \ZZ^{n+1}$ carry over to $\TT$ as a unimodular triangulation of $P$.


Before continuing with toric ideals, let us first recall some additional definitions.
Let $\Delta$ be an abstract simplicial complex on vertex set $\{v_1,\ldots,v_s\}$ and let $T = k[t_1,\ldots,t_s]$.
The {\em Stanley-Reisner} ideal of $\Delta$ is
\[ I_{\Delta} := ( t_{i_1}\cdots t_{i_j}\ |\ \{i_1,\ldots,i_j\} \notin \Delta),\]
where the parentheses represent the ideal of $T$ generated by these monomials.
This definition leads us to the {\em Stanley-Reisner ring}, $T/I_{\Delta}$, whose monomials are those with support corresponding to faces of $\Delta$.
The numerator of its Hilbert series is called the $h$-polynomial of $\Delta$.
If $P$ is a polytope and $\Delta$ is a unimodular triangulation of $P$, then the $h$-polynomial of $\Delta$ and the $h^*$-polynomial of $P$ coincide.

Note that the Stanley-Reisner ideal of a simplicial complex accounts for the combinatorial structure of the complex and does not inherently reflect any geometric properties.
To overcome this limitation, we will express the Stanley-Reisner ideal as the result of operations on a different ideal, designed with geometric properties in mind.

%%%%%

Now, suppose $\prec$ is a monomial order on $T$,
that is, a total well-ordering of the monomials of $T$ which respects multiplication.  Consider any ideal $I$  of $T$.
Each $f \in I$ then has an {\em initial} or {\em leading term} with respect to $\prec$, denoted $\init(f)$, which is the term of $f$ that is greatest with respect to $\prec$.
The {\em initial ideal} of $I$ with respect to $\prec$ is the ideal generated by the initial terms of polynomials in $I$, that is,
\[
	\init(I) := ( \init(f)\ |\ f \in I).
\]
A {\em Gr\"obner basis} of $I$ is a finite generating set $\grob$ for $I$ such that $\init(I) = (\init(g)\ |\ g \in \grob)$.
Since $I$ is assumed to be an ideal of a Noetherian ring, a Gr\"obner basis always exists and may be computed from a given finite set of generators for $I$ using the well-known Buchberger algorithm.
Say $\grob$ is {\em reduced} if each element has a leading coefficient of $1$ and for any $g_1, g_2 \in \grob$, $\init(g_1)$ does not divide any term of $g_2$.
Given an ideal $I \subseteq T$ and a fixed monomial ordering on $T$, there are many Gr\"obner bases of $I$ but there is exactly one reduced Gr\"obner basis of $I$.

There are many nice results connecting Gr\"obner bases with combinatorics, one of which involves types of triangulations that we define now.
Suppose $P \subseteq \RR^n$ is an $n$-dimensional lattice polytope and $P \cap \ZZ^n = \{l_1,\ldots,l_s\}$.
Choose some vector $w = (w_1,\ldots,w_s) \in \RR^s$ such that the polytope
\[ P_w := \conv\{(l_1,w_1),\ldots,(l_s,w_s)\} \subseteq \RR^{n+1}\]
is $(n+1)$-dimensional, i.e., $P_w$ does not lie in an affine hyperplane of $\RR^{n+1}$.
Certain facets of $P_w$ have outward-pointing normal vectors with a negative last coordinate; projecting these facets back to $\RR^n$ provides the facets of a polytopal decomposition of $P$.
If the facets are themselves simplices, then the decomposition is a triangulation.
Triangulations obtainable in this way for some $w$ are called {\em regular}, and will be denoted $\Upsilon_w(P)$.


There is a close connection between regular triangulations of $\conv(\A)$, where $\A \subseteq \ZZ^n$ is a configuration of size $s$, and initial ideals of $I_{\A}$.
First, we note that each monomial ordering $\prec$ on $T_{\A} = k[t_1,\dots,t_{s}]$ can be represented by a sufficiently generic {\em weight vector} $w \in \RR^{s}$ such that, for all $u, v \in \ZZ_{\geq 0}^{s}$, $t^u \prec t^v$ if and only if $w^Tu < w^Tv$.
Next, we define the {\em initial complex} $\Delta_{\prec}(I)$ of an ideal $I \subseteq T_{\A}$ with respect to $\prec$ to be the simplicial complex on $[s]$ such that $F$ is a face of $\Delta_{\prec}(I)$ if and only if there is no monomial in $\init(I)$ whose support is $F$.
Using linear programming, one may show the following. 


\begin{thm}[Theorem~8.3,\cite{sturmfels}]\label{thm:sturmfels1}
	Let $\A \subseteq \ZZ^n$ be a configuration.
	If $w$ is the weight vector for a monomial order $\prec$ on $T_{\A}$, then $\Delta_{\prec}(I_{\A})$, an abstract simplicial complex, is geometrically the regular triangulation $\Upsilon_w(\conv(\A))$. \qed
\end{thm}

Two other important connections given in \cite{sturmfels} are summarized below.

\begin{thm}[Corollary~8.4 and Corollary~8.9, \cite{sturmfels}]\label{thm:sturmfels2}
	For any monomial order $\prec$ and corresponding weight vector $w$, the radical $\rad(\init(I_{\A}))$ is the Stanley-Reisner ideal of $\Upsilon_w(\conv(\A))$.
	Moreover, $\init(I_{\A})$ is squarefree if and only if $\Upsilon_w(\conv(\A))$ is unimodular with respect to the affine lattice generated by $\ZZ$-linear combinations of points in $\A$. \qed
\end{thm}

The triangulations $\TT_n(132,312)$ and $\AltT_n(123)$ will turn out to have another property as well.
We demonstrate these by taking the vertices of $P = B_n(132,312)$ (respectively, $P = \AltB_n(123)$) and imposing a certain graded reverse lexicographic (grevlex) monomial ordering on $T_{\A_P} / I_{\A_P}$ induced from $Q_n(132,312)$ (respectively, $Q = \AltQ_n(123)$).
This allows us to define a {\em reverse lexicographic}, or {\em pulling}, triangulation of a lattice polytope $P$, which is any triangulation whose Stanley-Reisner ideal is $\rad\left({\text{in}_{\lglex}(I_P)}\right)$.
Thus, a reverse lexicographic triangulation of $P$ may be described as the triangulation whose maximal simplices are the projections of the appropriate facets of $P_w$ where $w$ is a weight vector for $\lglex$.

We now have all the definitions in place to state our main result of this section.  It is proved by constructing, in each of the two cases, a reduced Gr\"obner basis for $I_{\A_P}$ with respect to grevlex order and then appealing to the two previous results and \cref{prop:unimodularity}.

\begin{thm}\label{thm:regularity}
	The sets $\TT_n(132,312)$ and $\AltT_n(123)$ are shellable, regular, unimodular reverse lexicographic triangulations of $B_n(132,312)$ and $\AltB_n(123)$, respectively. \qed
\end{thm}

Because the above triangulations are grevlex triangulations, Corollary~2.5 of \cite{StanleyDecompositions} gives
\begin{equation}
	h^*(B_n(132,312)) = h(\TT_n(132,312)) = h(\Delta(Q_n(132,312))), \label{eq:h*-vector is h-vector}
\end{equation}
and likewise for $\AltB_n(123)$.
This fact comes into play in the next section when making statements about the components of $h^*$-vectors for our polytopes.

\section{The Ehrhart Theory of $B_n(132,312)$ and $\AltB_n(123)$}\label{sec:gorensteinsection}

The previous section identified shellable, regular, and unimodular triangulations of $B_n(132,312)$ and $\AltB_n(123)$ which arose from order complexes of certain distributive lattices;
in this section, we use the EL-labelings of the lattices to study the $h^*$-vectors of the polytopes.
To do so, we require some more definitions and background.

Suppose $P \subseteq \RR^n$ is a lattice polytope containing the origin in its interior.
We say that $P$ is {\em reflexive} if its polar dual
\[
	P^{\vee} := \{x \in \RR^n\ |\ x^Ty \leq 1 \text{ for all } y \in P\}
\]
is also a lattice polytope. 
Any lattice translate of a reflexive polytope is also called reflexive.
A lattice polytope $P$ is said to be {\em Gorenstein} if $kP$ is reflexive for some $k$, called the {\em index}. 
Stanley \cite[Theorem 4.4]{StanleyHilbert} proved that a lattice polytope is Gorenstein if and only if its $h^*$-vector is palindromic.

The main goal of this section will be to sketch a proof of the following theorem.

\begin{thm}\label{thm:gorenstein}
	For all $n$, the $h^*$-vectors of $B_n(132,312)$ and $\AltB_n(123)$ are palindromic and unimodal. 
\end{thm}

If the hyperplane description of a lattice polytope is known, then deciding whether its $h^*$-vector is palindromic is often a straightforward task.
Such a description of $B_n(132,312)$ and $\AltB_n(123)$ has been elusive, though, so we must approach the proof of \cref{thm:gorenstein} by showing the palindromic condition directly.

One benefit of going through the work of the previous section is that once a Gorenstein polytope is known to have a regular, unimodular triangulation, 
it follows that the $h^*$-vector of the polytope is unimodal in addition to being palindromic~\cite{BrunsRomer}.
Thus, because of \cref{thm:regularity}, to demonstrate \cref{thm:gorenstein} it suffices to prove the palindromic condition.

We first need to recall some results about shellable triangulations.
In such a triangulation with shelling order $F_1,\dots,F_s$, the {\em restriction} of face $F_j$ is the set $\cR(F_j)$ of vertices $v\in F_j$ such that the facet $F_j-v$ is contained in $F_1\cup\dots\cup F_{j-1}$.  The {\em shelling number} of $F_j$ is $r(F_j)=|\cR(F_j)|$. 
The following result of Stanley shows that the entries of the $h^*$-vector of the polytope being shelled can be computed using shelling numbers.

\begin{prop}[Corollary 2.6, \cite{StanleyDecompositions}]
\label{StanleyDecomp}
	Suppose that $T_1,\ldots, T_k$ is a shelling order of a unimodular triangulation of a lattice polytope $P$. 
	Then the component $h^*_i$ of $h^*(P)$ is equal to the number of simplices $T_j$ such that $r(T_j) = i$. \qed
\end{prop}

When using EL-shellings, there is an easy way to determine the shelling number of a facet, that is, of a maximal chain $c$, from its labeling.  In particular, if 
\[
	\lambda(c)=(\lambda(q_0,q_1),\lambda(q_1,q_2),\dots, \lambda(q_{k-1},q_k))
\]
then $q_m\in \cR(c)$ if and only if we have a descent $\lambda(q_{m-1},q_m)>\lambda(q_m,q_{m+1})$ in $\lambda(c)$.  This is the content of the following lemma of Bj\"orner.
\begin{lemma}[Lemma 2.6, \cite{BjornerShellable}]\label{lem:shelling numbers}
	Let $c$ be a maximal chain of the poset $P$ admitting an EL-labeling $\lambda$, and let $\des \sigma$ note the number of descents in $\sigma \in \symm_n$. Then
\[\pushQED{\qed}
		r(c)=\des \lambda(c). \qedhere
\popQED
\]	
\end{lemma}

The last link in our chain will come from a result in the theory of $(Q,\om)$-partitions as developed by Stanley. A fuller exposition can be found in Chapter 3 of his book~\cite{StanleyVol1}.
Let $Q$ be a poset with $|Q| = n$, and let $\omega: Q \to [n]$ be a bijection, called a {\em labeling} of $Q$.
We say $f: Q \to \ZZ_{\geq 1}$ is a {\em (dual) $(Q,\omega)$-partition} if $f$ is order preserving, and, whenever $s < t$ and $\omega(s) > \omega(t)$, then $f(s) < f(t)$.

In a sense one may think of $\omega$ as indicating where strict inequalities of $f$ occur, rather than weak inequalities.
If $\omega$ itself is order-preserving then, as we have already seen,  it is called a {\em natural} labeling of $Q$.
We call $\omega$ {\em dual natural} if its {\em dual labeling} $\overline{\omega} : Q \to [n]$, defined by the complementation 
$\overline{\omega}(q) = n + 1 - q$, is natural.

We will be concerned with the {\em order polynomial} of $(Q,\om)$, denoted $\Om_{Q,\om}(m)$, which is the number of maps $f:Q\rightarrow[m]$ such that $f$ is order-preserving and, whenever $s < t$ and $\om(s) > \om(t)$, then $f(s) < f(t)$.
It can be shown that $\Om_{Q,\om}(m)$ is a polynomial in $m$ of degree $n=|Q|$.  Equivalently, the generating function for the order polynomial must be in the form
\[
	\sum_{m\ge0}  \Om_{Q,\om}(m) t^m  =\frac{A_{Q,\om}(t)}{(1-t)^{n+1}}
\]
where $A_{Q,\om}(t)$ is a polynomial of degree at most $n$ called the {\em Eulerian polynomial} of $(Q,\om)$.  In fact, one can give an explicit description of $A_{Q,\om}(t)$ as follows.  Define the {\em Jordan-H\"older set} of $(Q,\om)$, denoted $\LL(Q,\om)$, to be the set of all permutations of the form $w=\om(q_1)\om(q_2)\dots\om(q_n)$ as $q_1,q_2,\dots,q_n$ runs over all linear extensions of $Q$, that is, total orders on $Q$ such that if $q_i<q_j$ in $Q$ then $i<j$.

We thank Richard Stanley for pointing out that $(P,\omega)$-partitions could be used to prove the following result.
In particular, it is a consequence of Theorem 3.15.8, Corollary 3.15.12, and Corollary 3.15.18 of \cite{StanleyVol1}.

\begin{thm}
\label{Qpalin}
	Let $Q$ be a poset and let $\om$ be a natural labeling of $Q$.  Then the Eulerian polynomial $A_{Q,\om}(t)$ is palindromic if and only if $Q$ is graded. \qed
\end{thm}

The previous three results combined with \cref{thm:regularity} and equation~\eqref{eq:h*-vector is h-vector} prove the the following result. 

\begin{thm}\label{thm:hstarPalin}
	For all $n$, the $h^*$-vectors of $B_n(132,312)$ and $\AltB_n(123)$ are palindromic. \qed
\end{thm}

Now that we know the $h^*$-vectors sort the simplices of $\TT_n(132,312)$ and $\AltT_n(123)$ by their shelling number, and these triangulations are unimodular, then we can easily identify the normalized volume. 
We simply need to count the number maximal chains in the corresponding distributive lattices.
But by \cref{prop:distributive}, this amounts to counting the number of standard Young diagrams of appropriate shape.
Using the well-known hook formulas, established in \cite{Thrall} and \cite{FrameHookLength}, provides us the the normalized volumes.

\begin{cor}
	The normalized volume of $B_n(132,312)$ is
	\[
		\Vol B_n(132,312) = \binom{n}{2}!\frac{\prod_{i=1}^{n-1} (i-1)!}{\prod_{i=1}^{n-1} (2i-1)!}
	\]
	Setting $k = \lceil n/2 \rceil,$ the normalized volume of $\AltB_n(123)$ is 
	\[\pushQED{\qed}
		\Vol \AltB_n(123) = \binom{k}{2}!\frac{1}{\prod_{i=1}^{k-1}(2i -1)^{k-i}}. \qedhere
	\popQED
	\]
\end{cor}

\printbibliography



\end{document}